package com.zjsru.plan2025.oneday;

import java.util.ArrayList;
import java.util.List;

/**
 * 386. 字典序排数
 *
 * @Author: cookLee
 * @Date: 2025-06-08
 */
public class LexicalOrder {

    /**
     * 主
     * \
     * 给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数
     * \
     * 输入：n = 13
     * 输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        LexicalOrder lexicalOrder = new LexicalOrder();
        int n = 13;
        System.out.println(lexicalOrder.lexicalOrder(n));
    }

    /**
     * 词汇顺序
     *
     * @param n n
     * @return {@link List}<{@link Integer}>
     */
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            if (i > n) {
                break;
            } else {
                ans.add(i);
                this.helper(i, n, ans);
            }
        }
        return ans;
    }

    private void helper(int i, int n, List<Integer> ans) {
        for (int j = 0; j < 10; j++) {
            if (i * 10 + j > n) {
                break;
            } else {
                ans.add(i * 10 + j);
                //迭代计算后续字典纸满足要求的数字
                this.helper(i * 10 + j, n, ans);
            }
        }
    }


    /**
     * 词法排序2
     *
     * @param n n
     * @return {@link List}<{@link Integer}>
     */
    public List<Integer> lexicalOrder2(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        int number = 1;
        for (int i = 0; i < n; i++) {
            ret.add(number);
            if (number * 10 <= n) {
                number *= 10;
            } else {
                // 如果当前数字的个位数是9，或者加上1后大于n，则需要回溯到上一个数字的十位数。
                while (number % 10 == 9 || number + 1 > n) {
                    number /= 10;
                }
                number++;
            }
        }
        return ret;
    }

}
